package leetcode.lcp.lcp20230422;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

//Solution4Test
public class Solution4 {

	int m, n;
	char[][] mz;
	int p, q;

	public int challengeOfTheKeeper(String[] maze) {
		m = maze.length;
		n = maze[0].length();
		mz = new char[m][n];
		int[] start = null;
		Integer[][] mins = new Integer[m][n];
//		for (int i = 0; i < m; i++) {
//			Arrays.fill(mins, -1);
//		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				char c = maze[i].charAt(j);
				mz[i][j] = c;
				if (c == 'S') {
					start = new int[] { i, j };
				} else if (c == 'T') {
					p = i;
					q = j;
				}
			}
		}
		mins[p][q] = 0;
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { p, q, 0 });
		while (!queue.isEmpty()) {
			int[] c = queue.poll();
			int x = c[0], y = c[1], z = c[2] + 1;
			for (int i = 0; i < 8; i += 2) {
				int nextx = x + d[i], nexty = y + d[i + 1];
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && mins[nextx][nexty] == null
						&& mz[nextx][nexty] != '#') {
					mins[nextx][nexty] = z;
					queue.add(new int[] { nextx, nexty, z });
				}
			}
		}
		if (mins[start[0]][start[1]] == null) {
			return -1;
		}
		return 0;
	}

	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

}
